1.67

题目

Let the rotational closure of language $A$ be

R C (A) = {y x ∣ x y \in A} .

a. Show that for any language $A$ , we have $R C (A) = R C (R C (A)) .$
b. Show that the class of regular languages is closed under rotational closure.

思路

点击展开

a. 展开集合 $R C (R C (A))$ 的定义，画出图形示意，结论显然
b. 要判断字符串是否可以围绕某个分割点前后置换，变成 $L (A)$ ，这是个多选择过程，考虑构造 NFA，不同分割点的选择对应不同 $ε$ 转移

解答

点击展开

R C (R C (A)) = {x ∣ x = m n, n m = p q, q p \in A}

不妨设 $p q$ 分割点在 $n m$ 分割点右侧，即 $| p | > | n |$ ，两个切割点将 $n m$ 分为三段：

n, (m \land p), q

那么

q p = q n (m \land p) \in A

x = m n = (m \land p) q n \in R C (A)

所以 $R C (R C (A)) \subseteq R C (A)$ ，显然有 $R C (A) \subseteq R C (R C (A))$ ，故 $R C (R C (A)) = R C (A)$

b.
设 A 对应的 DFA 为 M，有 $k$ 个节点，那么把 DFA 复制为 $2 k$ 份，两两配对
这里假设 $k = 3$ ， $q_{3}$ 是 M 的接受节点， $q_{1}$ 是 M 的起始节点

三个子图共同构成了最终的 NFA，每个子图代表不同旋转分割点的选择。
输入 $ω = y x$ ，先在前半个子图中识别 $y$ ， $y$ 需要从分割点移动到 M 的接受状态；再经过 $ε$ 转移到后半个子图识别 $x$ ， $x$ 需要从 M 的起始状态移动到分割点。存在这样的路径等价于 $x y$ 能从 M 的起始状态移动到 M 的接受状态，即 $x y \in A$ ， $ω = y x \in R C (A)$